#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/10/17
# @Author   :Changshu
# @File     :Exercise_342.py
# 342. 4的幂
# 给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。

# 进阶：
# 你能不使用循环或者递归来完成本题吗？

'''使用循环
def isPowerOfFour(num: int) -> bool:
	n=num
	while n>3:
		if n%4!=0:
			return False
		n=n>>2
	if n==1:
		return True
	return False
'''

'''使用递归
def isPowerOfFour(num: int) -> bool:
	if num==1:
		return True
	if num==0 or num%4!=0:
		return False
	return isPowerOfFour(num>>2)
'''

'''进阶
	因为4的幂用二进制表示后，其中的1一定在奇数位
'''
def isPowerOfFour(num: int) -> bool:
	# 如果不是2的幂，直接返回false
	if num<=0 or num&(num-1)!=0:
		return False
	return 0x55555555&num==num


if __name__ == '__main__':
	for num in [0,1,4,5,65,64,256]:
	# num=
		print(isPowerOfFour(num))